#pragma once

#include <iostream>
#include <vector>
#include <string>
#include <assert.h>

using namespace std;

enum Color
{
	RED,
	BLACK
};

template<class T>
struct RBTNode
{
	RBTNode(const T& value)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _val(value)
		, _col(RED)
	{}

	RBTNode<T>* _left;
	RBTNode<T>* _right;
	RBTNode<T>* _parent;
	T _val;
	Color _col;
};

template<class T, class Ref, class Ptr>
struct RBTIterator
{
	typedef RBTNode<T> Node;
	typedef RBTIterator<T, Ref, Ptr> iterator;

	Node* _node;

	RBTIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_val;
	}

	Ptr operator->()
	{
		return &_node->_val;
	}

	iterator& operator++()
	{
		Node* parent = _node->_parent;
		if (_node->_right == nullptr)
		{
			while (parent && _node == parent->_right)
			{
				_node = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		else
		{
			Node* right = _node->_right;
			while (right->_left) right = right->_left;
			_node = right;
		}
		return *this;
	}

	// it++
	iterator operator++(int)
	{
		iterator temp = _node;
		Node* parent = _node->_parent;
		if (_node->_right == nullptr)
		{
			while (parent && _node == parent->_right)
			{
				_node = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		else
		{
			Node* right = _node->_right;
			while (right->_left) right = right->_left;
			_node = right;
		}
		return temp;
	}

	iterator& operator--()
	{
		Node* left = _node->_left;
		if (left)
		{
			while (left->_right) left = left->_right;
			_node = left;
		}
		else
		{
			Node* parent = _node->_parent;
			while (parent && parent->_left == _node)
			{
				_node = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const iterator& it)
	{
		return _node != it._node;
	}
};

template<class K, class T, class KeyOfT>
class RBTree
{
public:
	typedef RBTNode<T> Node;
	typedef RBTIterator<T, T&, T*> iterator;
	typedef RBTIterator<T, const T&, const T*> const_iterator;

	RBTree() = default;

	// t1(t2)
	RBTree(const RBTree& t)
	{
		_root = Copy(t._root);
	}

	// t1 = t2
	RBTree& operator=(RBTree t)
	{
		swap(_root, t._root);
		return *this;
	}

	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}

	iterator begin()
	{
		if (_root == nullptr) return nullptr;

		Node* cur = _root;
		while (cur->_left) cur = cur->_left;

		return cur;
	}

	iterator end()
	{
		return nullptr;
	}

	const_iterator begin() const
	{
		if (_root == nullptr) return nullptr;

		Node* cur = _root;
		while (cur->_left) cur = cur->_left;

		return cur;
	}

	const_iterator end() const
	{
		return nullptr;
	}

	pair<iterator, bool> insert(const T& value)
	{
		if (_root == nullptr)
		{
			_root = new Node(value);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}

		Node* parent = nullptr;
		Node* cur = _root;

		KeyOfT kot;
		while (cur)
		{
			if (kot(value) < kot(cur->_val))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(value) > kot(cur->_val))
			{
				parent = cur;
				cur = cur->_right;
			}
			else return make_pair(iterator(cur), false);
		}

		Node* newnode = new Node(value);
		newnode->_parent = parent;
		if (kot(value) < kot(parent->_val)) parent->_left = newnode;
		else parent->_right = newnode;

		cur = newnode;

		while (cur->_parent && cur->_parent->_col == RED)
		{
			Node* father = cur->_parent;
			Node* grandparent = father->_parent;
			if (father == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					father->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					cur = grandparent;
				}
				else
				{
					if (cur == father->_left)
					{
						RotateR(grandparent);
						father->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						RotateL(father);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					father->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					cur = grandparent;
				}
				else
				{
					if (cur == father->_right)
					{
						RotateL(grandparent);
						father->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						RotateR(father);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;

		return make_pair(iterator(newnode), true);
	}

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* grandparent = parent->_parent;
		Node* curR = cur->_right;

		parent->_left = curR;
		if (curR) curR->_parent = parent;
		parent->_parent = cur;
		cur->_right = parent;

		cur->_parent = grandparent;
		if (grandparent)
		{
			if (parent == grandparent->_left) grandparent->_left = cur;
			else grandparent->_right = cur;
		}
		else _root = cur;
	}

	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* grandparent = parent->_parent;
		Node* curL = cur->_left;

		parent->_right = curL;
		if (curL) curL->_parent = parent;
		parent->_parent = cur;
		cur->_left = parent;

		cur->_parent = grandparent;
		if (grandparent)
		{
			if (parent == grandparent->_left) grandparent->_left = cur;
			else grandparent->_right = cur;
		}
		else _root = cur;
	}

	Node* find(const K& key)
	{
		KeyOfT kot;
		Node* cur = _root;
		while (cur)
		{
			if (key < kot(cur->_val)) cur = cur->_left;
			else if (key > kot(cur->_val)) cur = cur->_right;
			else return cur;
		}
		return nullptr;
	}

protected:
	Node* Copy(Node* root)
	{
		if (root == nullptr) return nullptr;

		Node* newnode = new Node(root->_val);

		newnode->_left = Copy(root->_left);
		if (newnode->_left) newnode->_left->_parent = newnode;

		newnode->_right = Copy(root->_right);
		if (newnode->_right) newnode->_right->_parent = newnode;

		return newnode;
	}

	void Destroy(Node* root)
	{
		if (root == nullptr) return;

		Destroy(root->_left);
		Destroy(root->_right);

		delete root;
	}

	Node* _root = nullptr;
};